package sortPackage;

/**
 * @program: jvm
 * @description
 * @author: tkk fendoukaoziji
 * @create: 2019-03-08 17:23
 **/

/**
 * 快速排序
 * 冒泡排序的改进，通过一趟排序将要排序的数据分割成独立两部分，其中一部分所有数据都比另外一部分数据
 * 要小， 然后按照这个方法对两部分数据分别进行快速排序，整个排序可以递归进行。
 * 一趟排序算法
 * 设置两个变量：left,right排序开始的时候 left-1，right=n
 * 取第一个元素作为关键数据，赋给temp变量
 * 从 r开始向前找，找到第一个比temp小的值，两者交换
 * 从前往后找，找到第一个比temp大的值，交换
 * 重复3.4知道r=j
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr={14,8,15,17,28,66,44,38,12,9};

        quickSort(arr,0,arr.length-1);
        for (int j=0;j<arr.length;j++) {
            System.out.print(arr[j]+" ");
        }
    }

    private static void quickSort(int[] arr, int low, int high) {
        int i=low;
        int j=high;
        if(low>high){
            return;
        }
        int key=arr[low];
        while(i<j){
            while(i<j&&arr[j]>key){//比基准值大 进入循环 否则  中断    找到了右侧比基准值小的
                j--;
            }
            while(i<j&&arr[i]<=key){//比基准值小进入循环  否则 中断  找到了左侧比基准值大的
                i++;
            }
            //交换 两个值
            if(i<j){
                int swap=arr[j];
                arr[j]=arr[i];
                arr[i]=swap;
            }
        }
        //交换key值
        arr[low]=arr[i];
        arr[i]=key;
        quickSort(arr,low,i-1);
        quickSort(arr,i+1,high);
    }


}

























